from bisect import bisect_right


class Calendar(object):
    """An event schedule for the stacking problem with interval release and due dates. Each 
    instant consists of a timestamp T and four sets of items: 
        1) release starts  - items which may enter the warehouse from this date
        2) release ends    - items which must be delivered at most on this date
        3) delivery starts - items which may be delivered from this date
        4) delivery ends   - items which must be delivered at most on this date
    A cursor to the calendar can be obtained by calling the cursor() method. Each cursor object 
    maintains its own position in the calendar, meaning that multiple cursors on the same calendar 
    can be used without affecting each other."""
    def __init__(self, items=()):
        self.timestamps = list()  # [timestamp] (ordered)
        self.events     = dict()  # {timestamp: (r_starts, r_ends, d_starts, d_ends)}
        self.items      = dict()  # {id: Item}
        for item in items:
            self.add(item)
            
    def __iter__(self):
        for timestamp in self.timestamps:
            yield timestamp, self.events[timestamp]
            
    def cursor(self):
        return Cursor(self)
        
    def add(self, item):
        if item.id in self.items:
            raise ValueError("duplicate item id in calendar")
        self.items[item.id] = item
        if item.release is not None:
            # Create calendar entries for any new timestamps
            self._add_timestamp(item.release.start)
            self._add_timestamp(item.release.end)
            # Update the calendar
            self.events[item.release.start][0].add(item)
            self.events[item.release.end][1].add(item)
        if item.due is not None:
            # Create calendar entries for any new timestamps
            self._add_timestamp(item.due.start)
            self._add_timestamp(item.due.end)
            # Update the calendar
            self.events[item.due.start][2].add(item)
            self.events[item.due.end][3].add(item)
            
    def _add_timestamp(self, timestamp):
        if timestamp not in self.events:
            self.events[timestamp] = (set(), set(), set(), set())
            index = bisect_right(self.timestamps, timestamp)
            self.timestamps.insert(index, timestamp)
            
            
class Cursor(object):
    """A cursor marks a position on a calendar. Items must be marked as delivered or released 
    before advancing the cursor to the next instant in the calendar."""
    def __init__(self, calendar):
        self.calendar      = calendar  # Calendar object this cursor will iterate over
        self.position      = None      # Calendar iterator
        self.timestamp     = None      # timestamp of the current instant
        self.released      = set()     # set of items released so far
        self.delivered     = set()     # set of items delivered so far
        self.release_ends  = set()     # items which MUST be released in the current instant
        self.delivery_ends = set()     # items which MUST be delivered in the current instant
        self.releases      = set()     # items which MAY be released in the current instant
        self.deliveries    = set()     # items which MAY be delivered in the current instant
        self.awaiting_release = set()  # set of items whose delivery interval has already 
                                       # started, but which are not in the 'deliveries' set  
                                       # because they haven't been released yet
        self.released.update(i for i in self.calendar.items.itervalues() if i.release is None)
        
    def __iter__(self):
        return self
        
    def next(self):
        self.advance()
        return self.timestamp
        
    def advance(self):
        if self.position is None:
            self.position = iter(self.calendar)
        if len(self.release_ends - self.released) > 0:
            raise Exception("some unreleased items must be released in the current instant")
        if len(self.delivery_ends - self.delivered) > 0:
            raise Exception("some undelivered items must be delivered in the current instant")
        timestamp, (r_starts, r_ends, d_starts, d_ends) = self.position.next()
        self.timestamp     = timestamp
        self.release_ends  = r_ends
        self.delivery_ends = d_ends
        self.releases.update(r_starts)
        self.deliveries.update(d_starts & self.released)
        self.awaiting_release.update(d_starts - self.released)
        
    def delivered_item(self, item):
        self.deliveries.remove(item)
        self.delivered.add(item)
        
    def released_item(self, item):
        self.releases.remove(item)
        self.released.add(item)
        if item in self.awaiting_release:
            self.awaiting_release.remove(item)
            self.deliveries.add(item)
            
            
